package main

// 84. 柱状图中最大的矩形
func main() {

	heights := []int{2, 1, 5, 6, 2, 3}
	//heights = []int{1, 1}
	area := largestRectangleArea1(heights)
	println(area)

}

func largestRectangleArea1(heights []int) int {
	var leftStack, rightStack []int
	numsLen := len(heights)
	leftMin := make([]int, numsLen)
	rightMin := make([]int, numsLen)

	// 找到每个节点，左边比自己第一个小的在差值, 从左往右那比自己大的就要出栈
	for idx, h := range heights {
		for len(leftStack) > 0 && heights[leftStack[len(leftStack)-1]] >= h {
			leftStack = leftStack[:len(leftStack)-1]
		}
		if len(leftStack) > 0 {
			leftMin[idx] = leftStack[len(leftStack)-1]
		} else {
			leftMin[idx] = -1
		}
		leftStack = append(leftStack, idx)
	}

	// 找到每个节点，右边比自己第一个小的在哪里, 更新踢出的值
	for idx, h := range heights {
		for len(rightStack) > 0 && heights[rightStack[len(rightStack)-1]] > h {
			rightMin[rightStack[len(rightStack)-1]] = idx
			rightStack = rightStack[:len(rightStack)-1]
		}
		rightStack = append(rightStack, idx)
	}
	for _, tak := range rightStack {
		rightMin[tak] = len(heights)
	}

	maxRes := 0

	for idx, n := range heights {
		idxLeftMinIdx := leftMin[idx]
		idxRightMinIdx := rightMin[idx]

		currMax := (idxRightMinIdx - idxLeftMinIdx - 1) * n
		if currMax > maxRes {
			maxRes = currMax
		}
	}

	return maxRes
}

func largestRectangleArea(heights []int) int {
	// 思路，每个参与柱状图的下标，需要找到左右比自己更小的边界
	// 先单边考虑，每个下标，找到左边比自己小的点的位置，和每日温度的求解思路是一样的，单调栈！
	// 单调栈存储左边的下标，如果左边的下标值大于自己，那就让它出栈
	// 存储左右单调栈结果，数组保存的是上一个比自己小的坐标，以及下一个比自己小的坐标，两个

	leftAns := make([]int, len(heights))
	rightAns := make([]int, len(heights))

	var leftStack []int
	for i := 0; i < len(heights); i++ {
		for len(leftStack) > 0 && heights[leftStack[len(leftStack)-1]] >= heights[i] {
			leftStack = leftStack[:len(leftStack)-1]
		}
		if len(leftStack) > 0 {
			// 那么左边比它小的下标为最后一个Stack
			leftAns[i] = leftStack[len(leftStack)-1]
		} else {
			leftAns[i] = -1
		}
		leftStack = append(leftStack, i)
	}

	var rightStack []int
	for i := len(heights) - 1; i >= 0; i-- {
		for len(rightStack) > 0 && heights[rightStack[len(rightStack)-1]] >= heights[i] {
			rightStack = rightStack[:len(rightStack)-1]
		}
		if len(rightStack) > 0 {
			// 那么右边边比它小的下标为最后一个Stack
			rightAns[i] = rightStack[len(rightStack)-1]
		} else {
			rightAns[i] = len(heights)
		}
		rightStack = append(rightStack, i)
	}

	maxRes := 0
	// 根据左右得到的结论，来计算最大的面积
	for i := 0; i < len(heights); i++ {
		leftWall := leftAns[i]
		rightWall := rightAns[i]
		height := heights[i]

		currArea := (rightWall - leftWall - 1) * height

		if currArea > maxRes {
			maxRes = currArea
		}
	}

	return maxRes
}

// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//
//求在该柱状图中，能够勾勒出来的矩形的最大面积。
//
//示例 1:
//
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
//示例 2：
//
//输入： heights = [2,4]
//输出： 4
//
//提示：
//
//1 <= heights.length <=105
//0 <= heights[i] <= 104
